#include <vector>
using namespace std;
class Solution
{
public:
    vector<vector<int>> permute(vector<int> &nums)
    {
        vector<vector<int>> res;
        vector<int> temp;
        dfs(res, nums, temp);
        return res;
    }
    // DFS全排列
    /**外层循环枚举每个数，
    内层循环检查这个数有没有用过，
    如果没用过就加入递归，
    回溯时弹出恢复状态。*/
    void dfs(vector<vector<int>> &res, vector<int> &nums, vector<int> &temp)
    {
        if (temp.size() == nums.size()) // 找到一个全排列
        {
            res.push_back(temp);
            return;
        }

        for (int i = 0; i < nums.size(); ++i) // 遍历nums中的每个元素
        {
            int j;
            for (j = 0; j < temp.size(); ++j) // 检查当前元素是否已在temp中
            {
                if (nums[i] == temp[j]) // 已存在，跳过
                    break;              // 跳出内层循环
            }
            if (j == temp.size()) // 当前元素不在temp中，加入temp继续DFS
            {
                temp.push_back(nums[i]);
                dfs(res, nums, temp);
                temp.pop_back();
            } // 回溯，移除最后一个元素
        }
    }
};